//
//  Problem553.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/31.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 553. 最优除法
 给定一组正整数，相邻的整数之间将会进行浮点除法操作。例如， [2,3,4] -> 2 / 3 / 4 。

 但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，才能得到最大的结果，并且返回相应的字符串格式的表达式。你的表达式不应该含有冗余的括号。

 示例：
     输入: [1000,100,10,2]
     输出: "1000/(100/10/2)"
     解释:
     1000/(100/10/2) = 1000/((100/10)/2) = 200
     但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
     因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

     其他用例:
     1000/(100/10)/2 = 50
     1000/(100/(10/2)) = 50
     1000/100/10/2 = 0.5
     1000/100/(10/2) = 2
 说明:
     输入数组的长度在 [1, 10] 之间。
     数组中每个元素的大小都在 [2, 1000] 之间。
     每个测试用例只有一个最优除法解。
 */
@objcMembers class Problem553: NSObject {
    func solution() {
        print(optimalDivisionShu([1000,100,10,2]))
        print(optimalDivisionShu([2,3,4]))
        print(optimalDivisionShu([30,130,110,23, 433]))
    }
    
    /*
     想让结果最大，那么左右越大越好，右边越小越好
     动态规划
     1: 创建一个三维数组dp[len][len][2]
     2: dp[i][j][0]： 从 i ~ j 能计算出的最小值
        dp[i][j][1]： 从 i ~ j 能计算出的最大值
     3: dp[i][j][0] = min(dp[i][i+1][0]/dp[i+1][j][1], dp[i][i+2][0]/dp[i+2][j][1])
        dp[i][j][1] = max(dp[i][i+1][1]/dp[i+1][j][0], dp[i][i+2][1]/dp[i+2][j][0])
     */
    func optimalDivision(_ nums: [Int]) -> String {
        var dp = Array(repeating: Array(repeating: Array(repeating: -1.0, count: 2), count: nums.count), count: nums.count)
        var sdp = Array(repeating: Array(repeating: Array(repeating: "", count: 2), count: nums.count), count: nums.count)
        
        // 特例：数组len = 1
        for i in 0..<nums.count-1 {
            dp[i][i] = [Double(nums[i]), Double(nums[i])]
            sdp[i][i] = [String(nums[i]),String(nums[i])]
            dp[i][i+1] = [Double(nums[i])/Double(nums[i+1]), Double(nums[i])/Double(nums[i+1])]
            sdp[i][i+1] = [String(nums[i]) + "/" + String(nums[i+1]), String(nums[i]) + "/" + String(nums[i+1])]
        }
        dp[nums.count-1][nums.count-1] = [Double(nums[nums.count-1]), Double(nums[nums.count-1])]
        sdp[nums.count-1][nums.count-1] = [String(nums[nums.count-1]),String(nums[nums.count-1])]
        
        for i in 0..<dp.count {
            print(dp[i])
        }
        
        for i in 0..<dp.count {
            print(sdp[i])
        }

        let list = optimalDivisonDP(nums, &dp, &sdp, 0, nums.count-1)

        
        for i in 0..<dp.count {
            print(dp[i])
        }
        for i in 0..<dp.count {
            print(sdp[i])
        }
//        var str = sdp[0][nums.count-1][1]
        return sdp.first?.last?.last ?? ""
        
    }
    
    func optimalDivisonDP(_ nums: [Int], _ dp: inout [[[Double]]], _ sdp: inout [[[String]]], _ start: Int, _ end: Int) -> [Double] {
        print(start, end)
        if start > end {
            return [0, 0]
        }
        
        if dp[start][end][0] != -1 {
            return dp[start][end]
        }
    
        
        var minValue:Double = 1000
        var maxValue:Double = -1
        var minStr = ""
        var maxStr = ""
        for i in start..<end {
            let startList = optimalDivisonDP(nums, &dp, &sdp, start, i)
            let endList = optimalDivisonDP(nums, &dp, &sdp, i+1, end)
            if endList[1] == 0 || endList[0] == 0 {
                continue
            }
            print(start, i , i+1, end)
            print(startList, endList)
            if startList[0]/endList[1] < minValue  {
                minValue = startList[0]/endList[1]
                if end == i + 1  {
                    minStr = sdp[start][i][0] + "/"  + sdp[i+1][end][1]
                } else {
                    minStr = sdp[start][i][0] + "/(" + sdp[i+1][end][1] + ")"
                }
            }
            if startList[1]/endList[0] > maxValue {
                maxValue = startList[1]/endList[0]
                if end == i + 1 {
                    maxStr = sdp[start][i][1] + "/" + sdp[i+1][end][0]
                } else {
                    maxStr = sdp[start][i][1] + "/(" + sdp[i+1][end][0] + ")"
                }
                
            }
            print(minValue, minStr, maxValue, maxStr)
        }
        
        dp[start][end] = [minValue, maxValue]
        sdp[start][end] = [minStr, maxStr]
        
        return dp[start][end]
    }
    
    /*
     数学方法：
     a/b/c 能够添加括号的有2种： a/(b/c) 和 (a/b)/c
                       b          a * c                      a
     a/(b/c) => a / ( --- ) =>  -------                 =>  --- * c    =>  c
                       c            b                        b
     
                                          这2个比较的话
                 a      1           a                       a     1        1
     (a/b)/c => --- *  ---- =>   -------                => --- * ---   => ---
                 b      c          b*c                      b     c        c
     
     提示里面说明了：每个元素的大小都在 [2, 1000] 之间。 =>  c > 1/c  => 所有永远选择第一个方式
     
     =>  a/b/c/d => a/(b/c/d)
    */
    func optimalDivisionShu(_ nums: [Int]) -> String {
        if nums.count == 1 {
            return String(nums[0])
        } else if nums.count == 2 {
            return String(nums[0]) + "/" + String(nums[1])
        }
        var str = String(nums[0]) + "/("
        for i in 1..<nums.count-1 {
            str += String(nums[i]) + "/"
        }

        return str + String(nums[nums.count-1]) + ")"
    }
}

